package leetcode

func minimumTotal(triangle [][]int) int {
	count := len(triangle)
	if count == 0 {
		return 0
	}

	if count == 1 {
		if len(triangle[0]) == 0 {
			return 0
		}
		return triangle[0][0]
	}

	sums := make([]int, count)
	copy(sums, triangle[count-1])
	var min int

	for row := count - 2; row >= 0; row-- {
		for i := 0; i <= row; i++ {
			min = sums[i]
			if sums[i] > sums[i+1] {
				min = sums[i+1]
			}
			sums[i] = min + triangle[row][i]
		}
	}
	return sums[0]
}

func topToBottom(triangle [][]int) int {
	count := len(triangle)
	sums := make([]int, count)
	sums[0] = triangle[0][0]

	var i, j, min int

	for i = 1; i < count; i++ {
		sums[i] = sums[i-1] + triangle[i][i]
		for j = i - 1; j > 0; j-- {
			min = sums[j-1]
			if min > sums[j] {
				min = sums[j]
			}
			sums[j] = min + triangle[i][j]
		}
		sums[0] += triangle[i][0]
	}

	min = sums[0]
	for i = 1; i < count; i++ {
		if min > sums[i] {
			min = sums[i]
		}
	}
	return min
}
